package com.earthchen;

/**
 * 希尔排序
 *
 * @author earthchen
 * @date 2018/8/10
 **/
public class SheelSort {

    /**
     * 将数的个数设为n，取奇数k=n/2，将下标差值为k的数分为一组，构成有序序列。
     * <p>
     * 再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。
     * <p>
     * 重复第二步，直到k=1执行简单插入排序。
     *
     * 非稳定排序算法
     */
    public static void sort(int[] a) {
        int len = a.length;
        while (len != 0) {
            len = len / 2;
            //分组
            for (int i = 0; i < len; i++) {
                //元素从第二个开始
                for (int j = i + len; j < a.length; j += len) {
                    //k为有序序列最后一位的位数
                    int k = j - len;
                    //要插入的元素
                    int temp = a[j];
                    //从后往前遍历
                    while (k >= 0 && temp < a[k]) {
                        a[k + len] = a[k];
                        //向后移动len位
                        k -= len;
                    }
                    a[k + len] = temp;
                }
            }
        }
    }
}
